home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-19 / iritsm3s.zip / BSP2POLY.C < prev    next >
C/C++ Source or Header  |  1991-12-21  |  12KB  |  304 lines
  1. /******************************************************************************
  2. * Bsp2Poly.c - Bezier to polygon/polylines conversion routines.              *
  3. *******************************************************************************
  4. * Written by Gershon Elber, Mar. 90.                          *
  5. ******************************************************************************/
  6.  
  7. #include "cagd_loc.h"
  8.  
  9. static CagdPolygonStruct *BspC1Srf2Polygons(CagdSrfStruct *Srf, int FineNess,
  10.              CagdBType ComputeNormals, CagdBType FourPerFlat);
  11.  
  12. /*****************************************************************************
  13. * Routine to convert a single bspline surface to set of triangles         *
  14. * approximating it. FineNess is a finess control on result and the bigger it *
  15. * is more triangles may result. a value of 10 is a good start value.         *
  16. * NULL is returned in case of an error, otherwise list of CagdPolygonStruct. *
  17. *   This routine looks for C1 discontinuities in the surface and split it    *
  18. * into C1 continuous patches to invoke BspC1Srf2Polygons to gen. polygons.   *
  19. *****************************************************************************/
  20. CagdPolygonStruct *BspSrf2Polygons(CagdSrfStruct *Srf, int FineNess,
  21.              CagdBType ComputeNormals, CagdBType FourPerFlat)
  22. {
  23.     CagdRType u, v;
  24.     int UOrder = Srf -> UOrder,
  25.     VOrder = Srf -> VOrder,
  26.     ULength = Srf -> ULength,
  27.     VLength = Srf -> VLength;
  28.     CagdBType
  29.     HasUDiscont = BspKnotC1Discont(Srf -> UKnotVector, UOrder, ULength, &u),
  30.     HasVDiscont = BspKnotC1Discont(Srf -> VKnotVector, VOrder, VLength, &v);
  31.     CagdPolygonStruct *Poly;
  32.  
  33.     if (HasUDiscont || HasVDiscont) {
  34.     CagdSrfStruct
  35.         *Srf1 = HasUDiscont ? BspSrfSubdivAtParam(Srf, u, CAGD_CONST_U_DIR)
  36.                 : BspSrfSubdivAtParam(Srf, v, CAGD_CONST_V_DIR),
  37.         *Srf2 = Srf1 -> Pnext;
  38.     CagdPolygonStruct
  39.         *Poly1 = BspSrf2Polygons(Srf1, FineNess, ComputeNormals, FourPerFlat),
  40.         *Poly2 = BspSrf2Polygons(Srf2, FineNess, ComputeNormals, FourPerFlat);
  41.  
  42.     CagdSrfFreeList(Srf1);
  43.  
  44.     /* Chain the two lists together: */
  45.     for (Poly = Poly1; Poly -> Pnext != NULL; Poly = Poly -> Pnext);
  46.     Poly -> Pnext = Poly2;
  47.     Poly = Poly1;
  48.     }
  49.     else
  50.     Poly = BspC1Srf2Polygons(Srf, FineNess, ComputeNormals, FourPerFlat);
  51.  
  52.     return Poly;
  53. }
  54.  
  55. /*****************************************************************************
  56. * Routine to convert a single C1 continuouse bspline srf to set of triangles *
  57. * approximating it. FineNess is a finess control on result and the bigger it *
  58. * is more triangles may result. a value of 10 is a good start value.         *
  59. * NULL is returned in case of an error, otherwise list of CagdPolygonStruct. *
  60. *****************************************************************************/
  61. static CagdPolygonStruct *BspC1Srf2Polygons(CagdSrfStruct *Srf, int FineNess,
  62.              CagdBType ComputeNormals, CagdBType FourPerFlat)
  63. {
  64.     int i, j, FineNessU1, FineNessV1, FineNessU, FineNessV, BaseIndex;
  65.     CagdRType u, v, UMin, UMax, VMin, VMax, *Pt;
  66.     CagdPointType
  67.     PType = Srf -> PType;
  68.     CagdPtStruct PtCenter, *Pt1, *Pt2, *Pt3, *Pt4, *PtMesh, *PtMeshPtr;
  69.     CagdVecStruct NlCenter, *Nl1, *Nl2, *Nl3, *Nl4, *PtNrml;
  70.     CagdCrvStruct *Crv;
  71.     CagdPolygonStruct *Poly,
  72.     *PolyHead = NULL;
  73.  
  74.     if (!CAGD_IS_BSPLINE_SRF(Srf)) return NULL;
  75.  
  76.     /* Simple heuristic to estimate how many samples to compute. */
  77.     FineNessU = Srf -> ULength * FineNess / 10;
  78.     FineNessV = Srf -> VLength * FineNess / 10;
  79.  
  80.  
  81.     if (FineNessU < 2) FineNessU = 2;
  82.     if (FineNessV < 2) FineNessV = 2;
  83.     switch (_CagdLin2Poly) {
  84.     case CAGD_REG_POLY_PER_LIN:
  85.         break;
  86.         case CAGD_ONE_POLY_PER_LIN:
  87.         if (Srf -> UOrder == 2) FineNessU = 2;
  88.         if (Srf -> VOrder == 2) FineNessV = 2;
  89.         break;
  90.         case CAGD_ONE_POLY_PER_COLIN:
  91.         break;
  92.     }
  93.     FineNessU1 = FineNessU - 1;
  94.     FineNessV1 = FineNessV - 1;
  95.  
  96.     /* Current to surface property such as curvature is used as subdivison   */
  97.     /* criterion and the surface is subdivided, equally spaced in parametric */
  98.     /* space, using FineNess as number of subdivisions per axis.         */
  99.  
  100.     /* Allocate a mesh to hold all vertices so common vertices need not be   */
  101.     /* Evaluated twice, and evaluate the surface at these mesh points.         */
  102.     PtMeshPtr = PtMesh = (CagdPtStruct *) CagdMalloc(FineNessU * FineNessV *
  103.                             sizeof(CagdPtStruct));
  104.  
  105.     BspSrfDomain(Srf, &UMin, &UMax, &VMin, &VMax);
  106.  
  107.     for (i = 0; i < FineNessU; i++) {
  108.     u = UMin + (UMax - UMin) * i / ((CagdRType) FineNessU1);
  109.     Crv = BspSrfCrvFromSrf(Srf, u, CAGD_CONST_U_DIR);
  110.  
  111.     for (j = 0; j < FineNessV; j++) {
  112.         v = VMin + (VMax - VMin) * j / ((CagdRType) FineNessV1);
  113.         Pt = BspCrvEvalAtParam(Crv, v);
  114.         CagdCoerceToE3(PtMeshPtr -> Pt, &Pt, -1, PType);
  115.         PtMeshPtr++;
  116.     }
  117.  
  118.     CagdCrvFree(Crv);
  119.     }
  120.  
  121.     if (ComputeNormals) PtNrml = BspSrfMeshNormals(Srf, FineNessU, FineNessV);
  122.  
  123.     /* Now that we have the mesh, create the polygons. */
  124.     for (i = 0; i < FineNessU1; i++)
  125.     for (j = 0; j < FineNessV1; j++) {
  126.         BaseIndex = i * FineNessV + j;
  127.         Pt1 = &PtMesh[BaseIndex];        /* Cache the four flat corners. */
  128.         Pt2 = &PtMesh[BaseIndex + 1];
  129.         Pt3 = &PtMesh[BaseIndex + FineNessV + 1];
  130.         Pt4 = &PtMesh[BaseIndex + FineNessV];
  131.         if (ComputeNormals) {
  132.         Nl1 = &PtNrml[BaseIndex];
  133.         Nl2 = &PtNrml[BaseIndex + 1];
  134.         Nl3 = &PtNrml[BaseIndex + FineNessV + 1];
  135.         Nl4 = &PtNrml[BaseIndex + FineNessV];
  136.         }
  137.  
  138.         if (FourPerFlat) {  /* Eval middle point and create 4 triangles. */
  139.         CAGD_COPY_POINT(PtCenter, *Pt1);
  140.         CAGD_ADD_POINT(PtCenter, *Pt2);
  141.         CAGD_ADD_POINT(PtCenter, *Pt3);
  142.         CAGD_ADD_POINT(PtCenter, *Pt4);
  143.         CAGD_MULT_POINT(PtCenter, 0.25);
  144.  
  145.         if (ComputeNormals) {
  146.             /* Average the four normals to find the middle one. */
  147.             CAGD_COPY_VECTOR(NlCenter, *Nl1);
  148.             CAGD_ADD_VECTOR(NlCenter, *Nl2);
  149.             CAGD_ADD_VECTOR(NlCenter, *Nl3);
  150.             CAGD_ADD_VECTOR(NlCenter, *Nl4);
  151.             CAGD_NORMALIZE_VECTOR(NlCenter);
  152.         }
  153.  
  154.         Poly = _CagdMakePolygon(ComputeNormals, Pt1, Pt2, &PtCenter,
  155.                             Nl1, Nl2, &NlCenter);
  156.         CAGD_LIST_PUSH(Poly, PolyHead);
  157.         Poly = _CagdMakePolygon(ComputeNormals, Pt2, Pt3, &PtCenter,
  158.                                 Nl2, Nl3, &NlCenter);
  159.         CAGD_LIST_PUSH(Poly, PolyHead);
  160.         Poly = _CagdMakePolygon(ComputeNormals, Pt3, Pt4, &PtCenter,
  161.                                 Nl3, Nl4, &NlCenter);
  162.         CAGD_LIST_PUSH(Poly, PolyHead);
  163.         Poly = _CagdMakePolygon(ComputeNormals, Pt4, Pt1, &PtCenter,
  164.                                 Nl4, Nl1, &NlCenter);
  165.         CAGD_LIST_PUSH(Poly, PolyHead);
  166.         }
  167.         else {               /* Only two along the diagonal... */
  168.         Poly = _CagdMakePolygon(ComputeNormals, Pt1, Pt2, Pt3,
  169.                                 Nl1, Nl2, Nl3);
  170.         CAGD_LIST_PUSH(Poly, PolyHead);
  171.         Poly = _CagdMakePolygon(ComputeNormals, Pt3, Pt4, Pt1,
  172.                                 Nl3, Nl4, Nl1);
  173.         CAGD_LIST_PUSH(Poly, PolyHead);
  174.         }
  175.     }
  176.  
  177.     CagdFree((VoidPtr) PtMesh);
  178.     if (ComputeNormals) CagdFree((VoidPtr) PtNrml);
  179.  
  180.     return PolyHead;
  181. }
  182.  
  183. /*****************************************************************************
  184. * Routine to convert a single bspline surface to NumOfIsolines polylines list*
  185. * in each param. direction with SamplesPerCurve in each isoparametric curve. *
  186. * Polyline are always E3 of CagdPolylineStruct type.                 *
  187. * Iso parametric curves are sampled equally spaced in parametric space.         *
  188. * NULL is returned in case of an error, otherwise list of CagdPolylineStruct.*
  189. * Attempt is made to extract isolines along C1 discontinuities first.         *
  190. *****************************************************************************/
  191. CagdPolylineStruct *BspSrf2Polylines(CagdSrfStruct *Srf, int NumOfIsocurves,
  192.                              int SamplesPerCurve)
  193. {
  194.     int i, NumC1Disconts;
  195.     CagdRType u, v, UMin, UMax, VMin, VMax, *C1Disconts, *IsoParams;
  196.     CagdCrvStruct *Crv;
  197.     CagdPolylineStruct *Poly,
  198.     *PolyList = NULL;
  199.  
  200.     if (!CAGD_IS_BSPLINE_SRF(Srf)) return NULL;
  201.  
  202.     /* Make sure requested format is something reasonable. */
  203.     if (SamplesPerCurve < 1) SamplesPerCurve = 1;
  204.     if (SamplesPerCurve > CAGD_MAX_BEZIER_CACHE_ORDER)
  205.     SamplesPerCurve = CAGD_MAX_BEZIER_CACHE_ORDER;
  206.     if (NumOfIsocurves < 2) NumOfIsocurves = 2;
  207.  
  208.     BspSrfDomain(Srf, &UMin, &UMax, &VMin, &VMax);
  209.  
  210.     /* Compute discontinuities along the u axis and use that to determine    */
  211.     /* where to extract isolines along u.                     */
  212.     C1Disconts = BspKnotAllC1Discont(Srf -> UKnotVector, Srf -> UOrder,
  213.                      Srf -> ULength, &NumC1Disconts);
  214.     IsoParams = BspKnotParamValues(UMin, UMax, NumOfIsocurves, C1Disconts,
  215.                                 NumC1Disconts);
  216.     for (i = 0; i < NumOfIsocurves; i++) {
  217.     u = IsoParams[i];
  218.  
  219.     Crv = BspSrfCrvFromSrf(Srf, u, CAGD_CONST_U_DIR);
  220.     Poly = BspCrv2Polyline(Crv, SamplesPerCurve);
  221.     Poly -> Pnext = PolyList;
  222.     PolyList = Poly;
  223.     CagdCrvFree(Crv);
  224.     }
  225.     CagdFree((VoidPtr) IsoParams);
  226.  
  227.     /* Compute discontinuities along the v axis and use that to determine    */
  228.     /* where to extract isolines along v.                     */
  229.     C1Disconts = BspKnotAllC1Discont(Srf -> VKnotVector, Srf -> VOrder,
  230.                      Srf -> VLength, &NumC1Disconts);
  231.     IsoParams = BspKnotParamValues(VMin, VMax, NumOfIsocurves, C1Disconts,
  232.                                 NumC1Disconts);
  233.     for (i = 0; i < NumOfIsocurves; i++) {
  234.     v = IsoParams[i];
  235.  
  236.     Crv = BspSrfCrvFromSrf(Srf, v, CAGD_CONST_V_DIR);
  237.     Poly = BspCrv2Polyline(Crv, SamplesPerCurve);
  238.     Poly -> Pnext = PolyList;
  239.     PolyList = Poly;
  240.     CagdCrvFree(Crv);
  241.     }
  242.     CagdFree((VoidPtr) IsoParams);
  243.  
  244.     return PolyList;
  245. }
  246.  
  247. /*****************************************************************************
  248. * Routine to approx. a single bspline curve as a polyline with             *
  249. * 2^SamplesPerCurve samples. Polyline is always E3 CagdPolylineStruct type.  *
  250. * Curve is sampled equally spaced in parametric space, unless the curve is   *
  251. * linear in which the control polygon is simply being copied.             *
  252. * NULL is returned in case of an error, otherwise CagdPolylineStruct.         *
  253. *****************************************************************************/
  254. CagdPolylineStruct *BspCrv2Polyline(CagdCrvStruct *Crv, int SamplesPerCurve)
  255. {
  256.     int i, j, n,
  257.     IsNotRational = !CAGD_IS_RATIONAL_CRV(Crv),
  258.     MaxCoord = CAGD_NUM_OF_PT_COORD(Crv -> PType);
  259.     CagdRType *Polyline[CAGD_MAX_PT_SIZE], Scaler;
  260.     CagdPtStruct *NewPolyline;
  261.     CagdPolylineStruct *P;
  262.  
  263.     if (!CAGD_IS_BSPLINE_CRV(Crv)) return NULL;
  264.  
  265.     /* Make sure requested format is something reasonable. */
  266.     if (SamplesPerCurve < 1) SamplesPerCurve = 1;
  267.     if (SamplesPerCurve > CAGD_MAX_BEZIER_CACHE_ORDER)
  268.     SamplesPerCurve = CAGD_MAX_BEZIER_CACHE_ORDER;
  269.     if (Crv -> Order == 2 && (1 << SamplesPerCurve) < Crv -> Length) {
  270.         /* Make sure 2^SamplesPerCurve can hold the entire control polygon. */
  271.         for (i = 1, SamplesPerCurve = 0;
  272.          i < Crv -> Length;
  273.          i <<= 1, SamplesPerCurve++);
  274.     }
  275.  
  276.     n = 1 << SamplesPerCurve;
  277.  
  278.     P = CagdPolylineNew(n);
  279.     NewPolyline = P -> Polyline;
  280.  
  281.     /* Allocate temporary memory to hold evaluated curve. */
  282.     for (i = 0; i < CAGD_MAX_PT_SIZE; i++)
  283.     Polyline[i] = (CagdRType *) CagdMalloc(sizeof(CagdRType) * n);
  284.  
  285.     if (MaxCoord > 3) MaxCoord = 3;
  286.  
  287.     n = P -> Length = BspCrvEvalToPolyline(Crv, SamplesPerCurve, Polyline);
  288.  
  289.     for (i = n - 1; i >= 0; i--) {              /* Convert to E3 polyline. */
  290.     if (IsNotRational)
  291.         Scaler = 1.0;
  292.     else
  293.         Scaler = Polyline[0][i];
  294.  
  295.     for (j = 0; j < MaxCoord; j++)
  296.        NewPolyline[i].Pt[j] = Polyline[j+1][i] / Scaler;
  297.     for (j = MaxCoord; j < 3; j++)
  298.        NewPolyline[i].Pt[j] = 0.0;
  299.     }
  300.     for (i = 0; i < CAGD_MAX_PT_SIZE; i++) CagdFree((VoidPtr) Polyline[i]);
  301.  
  302.     return P;
  303. }
  304.